package aobing;

import java.util.*;

/**
 * MaxHeap
 *
 * @author Syzer
 * @Description 大顶堆
 * @Date 2021/6/15 9:30
 */
public class MaxHeap<T extends Comparable<T>> {
    private List<T> mHeap; // 存放元素的动态数组

    public MaxHeap() {

        this.mHeap = new ArrayList<>();
    }


    /**
     * 大顶堆的向上调整算法(添加节点的时候调用) 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * @param start
     *            -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
     */
    protected void filterup(int start) {

        int c = start; // 需要调整的节点的初始位置
        int p = (c - 1) / 2; // 当前节点的父节点的位置
        T tmp = mHeap.get(c); // 被调整节点的值

        while (c > 0) {
            // 父节点的值和被调整节点的值进行比较
            int cmp = mHeap.get(p).compareTo(tmp);
            if (cmp >= 0) {
                // 父节点大
                break;
            } else {
                // 被调整节点的值大，交换
                mHeap.set(c, mHeap.get(p));
                c = p;
                p = (c - 1) / 2;
            }
        }
        // 找到被调整节点的最终位置了
        mHeap.set(c, tmp);
    }


    /**
     * 大顶堆的向下调整算法(删除节点的时候需要调用来调整大顶堆)
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * @param start
     *            -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     * @param end
     *            -- 截至范围(一般为数组中最后一个元素的索引)
     */
    protected void filterdown(int start, int end) {

        int c = start; // 被下调节点的初始位置
        int l = 2 * c + 1; // 左孩子节点的位置
        T tmp = mHeap.get(c); // 当前节点的值(大小)

        while (l <= end) {
            // 当前节点的左右节点进行比较
            int cmp = mHeap.get(l).compareTo(mHeap.get(l + 1));
            // 取大的
            if (l < end && cmp < 0) {
                l++;
            }
            // 当前节点和大的那个再比较一下
            cmp = tmp.compareTo(mHeap.get(l));
            if (cmp >= 0) {
                // 当前节点大,不用动
                break;
            } else {
                // 当前节点小,交换
                mHeap.set(c, mHeap.get(l));
                c = l; // 更新当前节点的位置
                l = 2 * c + 1; // 更新当前节点的左孩子位置
            }
        }
        mHeap.set(c, tmp);
    }


    /**
     * 向大顶堆中插入新元素
     *
     * @param data
     */
    public void insert(T data) {

        int insertIndex = mHeap.size(); // 获取插入的位置
        // 将新元素插入到数组尾部
        mHeap.add(data);
        // 调用filterup函数，调整大顶堆
        filterup(insertIndex);
    }


    /**
     * 删除大顶堆中的data节点
     *
     * @param data
     * @return 返回-1表示出错, 返回0表示删除成功
     */
    public int remove(T data) {

        // 大顶堆空
        if (mHeap.isEmpty()) {
            return -1;
        }

        // 获取data在数组中的索引
        int index = mHeap.indexOf(data);
        if (index == -1) {
            return -1;
        }

        // 堆中元素的个数
        int size = mHeap.size();
        // 删除了data元素，需要用最后一个元素填补，然后调用filterdown算法进行调整
        mHeap.set(index, mHeap.get(size - 1)); // 用最后一个元素填补
        mHeap.remove(size - 1); // 删除最后一个元素

        if (mHeap.size() > 1 && index < mHeap.size()) {
            // 调整成大顶堆
            filterdown(index, mHeap.size() - 1);
        }
        return 0;
    }


    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < mHeap.size(); i++) {
            sb.append(mHeap.get(i) + " ");
        }
        return sb.toString();
    }

    private Map<Integer, Integer> map = new HashMap<>();

    /*public int[] topKFrequent(int[] nums, int k) {
        int[] heap = new int[k];
        Map<Integer, List<Integer>> countMap = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int maxCount = 0;;
        for(Map.Entry<Integer, Integer> m : map.entrySet()) {
            List<Integer> list = countMap.getOrDefault(m.getValue(), new ArrayList<>());
            list.add(m.getKey());
            countMap.put(m.getValue(), list);
            maxCount = m.getValue() > maxCount ? m.getValue() : maxCount;
        }
        int index = 0;
        for(int i = maxCount;i >= 1;i--) {
            if(index == k) break;
            List<Integer> valueList = countMap.get(i);
            if(valueList != null) {
                for(Integer value : valueList) {
                    heap[index] = value;
                    index++;
                }
            }
        }
        return heap;

    }*/

    public int[] topKFrequent(int[] nums, int k) {
        int[] heap = new int[k];
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int index = 0;
        for(Map.Entry<Integer, Integer> m : map.entrySet()) {
            if(index < k) {
                heap[index] = m.getKey();
                heapSortUp(heap, index);
                index++;
            } else {
                if(map.get(heap[0]) < m.getValue()) {
                    heap[0] = m.getKey();
                    heapSortDown(heap, 0, k - 1);
                }
            }
        }
        return heap;

    }

    //小顶堆向上排序，取最后一个值每次与父节点比较，直到父节点比当前节点小
    private void heapSortUp(int[] heap, int current) {
        int parent = (current - 1) / 2;
        int temp = heap[current];
        while(current > 0) {
            int compareValue = map.get(heap[parent]).compareTo(map.get(temp));
            if(compareValue <= 0) {
                break;
            } else {
                heap[current] = heap[parent];
                current = parent;
                parent = (current - 1) / 2;
            }
        }
        heap[current] = temp;
    }

    //改变了根的值，小顶堆向下排序，先左(2n+1)右(2n+2)比较，再取小的与父节点比较，小的往上走
    private void heapSortDown(int[] heap, int current, int end) {
        int maxIndex = 2 * current + 1;
        int temp = heap[current];
        while(maxIndex <= end) {
            int compareValue;
            if(maxIndex < end && map.get(heap[maxIndex]).compareTo(map.get(heap[maxIndex + 1])) > 0) {
                maxIndex++;
            }
            compareValue = map.get(temp).compareTo(map.get(heap[maxIndex]));
            if(compareValue <= 0) {
                break;
            } else {
                heap[current] = heap[maxIndex];
                current = maxIndex;
                maxIndex = 2 * current + 1;
            }
        }
        heap[current] = temp;
    }

    /*public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        for(int i = len / 2;i >= 0;i--) {
            heapSort(nums, i, len);
        }
        for(int i = 0;i < k - 1;i++) {
            int temp = nums[0];
            nums[0] = nums[len - 1 - i];
            nums[len - 1 - i] = temp;
            len--;
            heapSort(nums, 0, len);
        }
        return nums[0];
    }*/

    public void heapSort(int[] arr,int i,int end) {
        int left = i * 2 + 1,right = i * 2 + 2, current = i;
        if(left < end && arr[current] < arr[left]) {
            current = left;
        }
        if(right < end && arr[current] < arr[right]) {
            current = right;
        }
        if(current != i) {
            int temp = arr[i];
            arr[i] = arr[current];
            arr[current] = temp;
            heapSort(arr, current, end);
        }
    }

    //基于快排的选择方法：随机选择一个中间数，与right交换，在left到right-1区间将所有小于该数的值放左边，结束后交换回left+1位置。重复动作
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    public int quickSelect(int[] nums, int left, int right, int index) {
        int value = randomPartition(nums, left, right);
        if(value == index) {
            return nums[value];
        } else {
            return value < index ? quickSelect(nums, value + 1, right, index) : quickSelect(nums, left, value - 1, index);
        }
    }

    public int randomPartition(int[] nums, int left, int right) {
        int middle = random.nextInt(right - left + 1) + left;
        swap(nums, middle, right);
        int partition = left, x = nums[right];
        for(int i = left;i < right;i++) {
            if(nums[i] < x) {
                swap(nums, partition++, i);
            }
        }
        swap(nums, partition, right);
        return partition;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
//        int a[] = {5,3,1,1,1,3,73,1};
//        int[] ints = maxHeap.topKFrequent(a, 2);
//        System.out.println(Arrays.toString(ints));

        int b[] = {3,2,3,1,2,4,5,5,6};
        int kthLargest = maxHeap.findKthLargest(b, 4);
        System.out.println(kthLargest);

//        int a[] = {10, 40 ,30, 60, 90, 70, 20, 50 ,80};
//
//        //大顶堆
//        MaxHeap<Integer> maxHeap = new MaxHeap<>();
//
//        //添加元素
//        System.out.println("=== 依次添加元素：");
//        for(int i = 0; i < a.length; i++) {
//            System.out.println(a[i]);
//            maxHeap.insert(a[i]);
//        }
//
//        //生成的大顶堆
//        System.out.println("=== 生成的大顶堆：");
//        System.out.println(maxHeap);
//
//        //添加新元素85
//        int data = 85;
//        maxHeap.insert(data);
//        System.out.println("=== 添加新元素" + data + "之后的大顶堆：");
//        System.out.println(maxHeap);
//
//        //删除元素90
//        data = 90;
//        maxHeap.remove(data);
//        System.out.println("=== 删除元素" + data + "之后的大顶堆：");
//        System.out.println(maxHeap);

    }

}
